/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-07-25
 * Time: 15:07
 */


class ListNode {
      int val;
      ListNode next;
      ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

  ;

public class Test {

    public ListNode createList() {
        ListNode A = new ListNode(4);
        ListNode B = new ListNode(2);
        ListNode C = new ListNode(1);
        ListNode D = new ListNode(3);
        A.next = B;
        B.next = C;
        C.next = D;

        return A;
    }

    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        ListNode phead = new ListNode(-1);
        ListNode pphead = phead;
        ListNode cur = head;
        while(cur != null) {
            ListNode prev = cur;
            ListNode tmp = cur;
            ListNode minNode = cur;
            while(tmp.next != null) {
                if(tmp.next.val < minNode.val) {
                    prev = tmp;
                    minNode = tmp.next;
                }
                tmp = tmp.next;
            }
            if(minNode == prev) {
                cur = cur.next;
            }else if(cur.next == minNode) {
                ListNode curNext = minNode.next;
                pphead.next = minNode;
                minNode.next = cur;
                cur.next = null;
                cur = curNext;
            }else {
                ListNode curNext1 = cur.next;
                ListNode curNext2 = minNode.next;
                minNode.next = curNext1;
                prev.next = cur;
                cur.next = curNext2;
                pphead.next = minNode;
                pphead = pphead.next;
                cur = curNext1;
            }
        }
        return phead.next;
    }
}
